#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <float.h>

#include <algorithm>
#include <vector>
#include <list>

struct Point {
  Point(float x, float y) : x(x), y(y) { }
  Point() { }
  bool operator==(const Point &p) const {
    return x == p.x && y == p.y;
  }
  void Print() { printf("(%f, %f)", x, y); }

  float x;
  float y;
};

typedef std::list<Point> PointList;
typedef std::vector<Point> PointVector;


inline float GenCoord() { return (float)rand(); }

void GenPoints(PointVector *points, int n) {
  points->reserve(n);
  for (int i = 0; i < n; ++i) {
    points->push_back(Point(GenCoord(), GenCoord()));
  }
}

#define INF FLT_MAX

float Distance(const Point &p1, const Point &p2) {
  return sqrt(p1.x * p2.x + p1.y * p2.y);
}

struct Result {
  Result() : dist(INF) { }

  Result(float dist, const Point &pi, const Point &pj) : 
      dist(dist), pi(pi), pj(pj) { }

  void Print() {
    printf("dist=%f; ", dist);
    printf("pi=");
    pi.Print();
    printf("; pj=");
    pj.Print();
    printf("\n");
  }
  float dist;
  Point pi, pj;
};

void ClosestPointPairNaive(const PointVector &points, Result *result) {
  if (points.size() < 2) return;
  for (size_t i = 0; i < points.size(); ++i) {
    for (size_t j = i + 1; j < points.size(); ++j) {
      float dist = Distance(points[i], points[j]);
      if (dist < result->dist) {
        result->dist = dist;
        result->pi = points[i];
        result->pj = points[j];
      }
    }
  }
}

bool CmpByX(const Point &p1, const Point &p2) {
  if (p1.x < p2.x) return true;
  else if (p1.x > p2.x) return false;
  return p1.y < p2.y;
}

bool CmpByY(const Point &p1, const Point &p2) {
  if (p1.y < p2.y) return true;
  return false;
}

class Band {
public:
  Band(float center, float delta) : 
      left(center - delta), right(center + delta) { }

  bool Contains(float x) const { return x >= left && x <= right; }
private:
  float left, right;
};

void CollectBandPoints(const PointVector &Y, const Band &band, PointList *BY) {
  for (size_t i = 0; i < Y.size(); ++i) {
    if (band.Contains(Y[i].x)) BY->push_back(Y[i]);
  }
}
                       

void ClosestPointPairInBand(const PointList &BY, Result *result) {
  for (PointList::const_iterator it = BY.begin(); it != BY.end(); ++it) {
    PointList::const_iterator nit = it;
    ++nit;
    for (int i = 0; nit != BY.end() && i < 7; ++i, ++nit) {
      float dist = Distance(*it, *nit);
      if (dist < result->dist) {
        result->dist = dist;
        result->pi = *it;
        result->pj = *nit;
      }
    }
  }
}

// make sure no duplicated points
void ClosestPointPair(const PointVector &X, const PointVector &Y, 
                      Result *result) {
  if (X.size() != Y.size()) printf("unmatched X and Y size\n");
  if (X.size() <= 3) return ClosestPointPairNaive(X, result);

  int nleft = (X.size() + 1) / 2;

  PointVector LY, RY;
  LY.reserve(nleft);
  RY.reserve(X.size() - nleft);

  Point lp = X[nleft - 1];
  for (size_t i = 0; i < Y.size(); ++i) {
    if (Y[i].x > lp.x) {
      RY.push_back(Y[i]);
    }
    else if (Y[i].x < lp.x) {
      LY.push_back(Y[i]);
    }
    else if (Y[i].y > lp.y) {
      RY.push_back(Y[i]);
    }
    else {
      LY.push_back(Y[i]);
    }
  }

  PointVector LX(X.begin(), X.begin() + nleft);
  PointVector RX(X.begin() + nleft, X.end());

  Result left_result;
  ClosestPointPair(LX, LY, &left_result);

  Result right_result;
  ClosestPointPair(RX , RY, &right_result);
  if (left_result.dist < right_result.dist) {
    *result = left_result;
  }
  else {
    *result = right_result;
  }

  PointList BY;
  Band band(X[nleft].x, result->dist);
  CollectBandPoints(Y, band, &BY);
  if (BY.size() > 1) {
    Result band_result;
    ClosestPointPairInBand(BY, &band_result);
    if (band_result.dist < result->dist) {
      *result = band_result;
    }
  }
}

void ClosestPointPair(const PointVector &points, Result *result) {
  PointVector X(points);
  std::sort(X.begin(), X.end(), CmpByX);
  X.erase(std::unique(X.begin(), X.end()));

  PointVector Y(X);
  std::sort(Y.begin(), Y.end(), CmpByY);

  ClosestPointPair(X, Y, result);
}

void Test(int n) {
  PointVector points;
  GenPoints(&points, n);
  Result result;
  //ClosestPointPairNaive(points, &result);
  ClosestPointPair(points, &result);
  result.Print();
}

int main(int argc, const char *argv[]) {
  if (argc < 2) Test(100);
  else Test(atoi(argv[1]));
  return 0;
}

